﻿using System;
//using System.Collections.Generic;
using System.Linq;
using System.Text;
using C5;
using System.IO;

namespace Gaur
{
    class Nfa
    {
        private readonly int startState;
        private readonly int exitState;    // This is the unique accept state
        private readonly IDictionary<int, ArrayList<Transition>> trans;

        public Nfa(int startState, int exitState)
        {
            this.startState = startState;
            this.exitState = exitState;
            this.trans = new HashDictionary<int, ArrayList<Transition>>();
            if (!startState.Equals(exitState))
            {
                trans.Add(exitState, new ArrayList<Transition>());
            }
        }

        public int Start { get { return startState; } }

        public int Exit { get { return exitState; } }

        public IDictionary<int, ArrayList<Transition>> Trans
        {
            get { return trans; }
        }

        public void AddTrans(int s1, String lab, int s2)
        {
            ArrayList<Transition> s1Trans;
            if (trans.Contains(s1))
                s1Trans = trans[s1];
            else
            {
                s1Trans = new ArrayList<Transition>();
                trans.Add(s1, s1Trans);
            }
            s1Trans.Add(new Transition(lab, s2));
        }

        public void AddTrans(KeyValuePair<int, ArrayList<Transition>> tr)
        {
            // Assumption: if tr is in Trans, it maps to an empty list (end state)
            trans.Remove(tr.Key);
            trans.Add(tr.Key, tr.Value);
        }

        public override String ToString()
        {
            return "NFA start=" + startState + " exit=" + exitState;
        }

        // Construct the transition relation of a composite-state DFA from
        // an NFA with start state s0 and transition relation Trans (a
        // dictionary mapping int to arraylist of Transition).  The start
        // state of the constructed DFA is the epsilon closure of s0, and
        // its transition relation is a dictionary mapping a composite state
        // (a set of ints) to a dictionary mapping a label (a string) to a
        // composite state (a set of ints).

        static IDictionary<Set<int>, IDictionary<String, Set<int>>>
          CompositeDfaTrans(int s0, IDictionary<int, ArrayList<Transition>> trans)
        {
            Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);
            IQueue<Set<int>> worklist = new CircularQueue<Set<int>>();
            worklist.Enqueue(S0);
            // The transition relation of the DFA
            IDictionary<Set<int>, IDictionary<String, Set<int>>> res =
              new HashDictionary<Set<int>, IDictionary<String, Set<int>>>();
            while (!worklist.IsEmpty)
            {
                Set<int> S = worklist.Dequeue();
                if (!res.Contains(S))
                {
                    // The S -lab-> T transition relation being constructed for a given S
                    IDictionary<String, Set<int>> STrans =
                      new HashDictionary<String, Set<int>>();
                    // For all s in S, consider all transitions s -lab-> t
                    foreach (int s in S)
                    {
                        // For all non-epsilon transitions s -lab-> t, add t to T
                        foreach (Transition tr in trans[s])
                        {
                            if (tr.lab != null)
                            {        // Non-epsilon transition
                                Set<int> toState;
                                if (STrans.Contains(tr.lab))   // Already a transition on lab
                                    toState = STrans[tr.lab];
                                else
                                {                         // No transitions on lab yet
                                    toState = new Set<int>();
                                    STrans.Add(tr.lab, toState);
                                }
                                toState.Add(tr.target);
                            }
                        }
                    }
                    // Epsilon-close all T such that S -lab-> T, and put on worklist
                    IDictionary<String, Set<int>> STransClosed =
                      new HashDictionary<String, Set<int>>();
                    foreach (KeyValuePair<String, Set<int>> entry in STrans)
                    {
                        Set<int> Tclose = EpsilonClose(entry.Value, trans);
                        STransClosed.Add(entry.Key, Tclose);
                        worklist.Enqueue(Tclose);
                    }
                    res.Add(S, STransClosed);
                }
            }
            return res;
        }

        // Compute epsilon-closure of state set S in transition relation Trans.  

        static Set<int>
          EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans)
        {
            // The worklist initially contains all S members
            IQueue<int> worklist = new CircularQueue<int>();
            S.Apply(worklist.Enqueue);
            Set<int> res = new Set<int>(S);
            while (!worklist.IsEmpty)
            {
                int s = worklist.Dequeue();
                foreach (Transition tr in trans[s])
                {
                    if (tr.lab == null && !res.Contains(tr.target))
                    {
                        res.Add(tr.target);
                        worklist.Enqueue(tr.target);
                    }
                }
            }
            return res;
        }

        // Compute a renamer, which is a dictionary mapping set of int to int

        static IDictionary<Set<int>, int> MkRenamer(ICollectionValue<Set<int>> states)
        {
            IDictionary<Set<int>, int> renamer = new HashDictionary<Set<int>, int>();
            int count = 0;
            foreach (Set<int> k in states)
                renamer.Add(k, count++);
            return renamer;
        }

        // Using a renamer (a dictionary mapping set of int to int), replace
        // composite (set of int) States with simple (int) States in the
        // transition relation Trans, which is a dictionary mapping set of
        // int to a dictionary mapping from string to set of int.  The
        // result is a dictionary mapping from int to a dictionary mapping
        // from string to int.

        static IDictionary<int, IDictionary<String, int>>
          Rename(IDictionary<Set<int>, int> renamer,
                 IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)
        {
            IDictionary<int, IDictionary<String, int>> newtrans =
              new HashDictionary<int, IDictionary<String, int>>();
            foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry
               in trans)
            {
                Set<int> k = entry.Key;
                IDictionary<String, int> newktrans = new HashDictionary<String, int>();
                foreach (KeyValuePair<String, Set<int>> tr in entry.Value)
                    newktrans.Add(tr.Key, renamer[tr.Value]);
                newtrans.Add(renamer[k], newktrans);
            }
            return newtrans;
        }

        static Set<int> AcceptStates(ICollectionValue<Set<int>> states,
                   IDictionary<Set<int>, int> renamer,
                   int exit)
        {
            Set<int> acceptStates = new Set<int>();
            foreach (Set<int> state in states)
                if (state.Contains(exit))
                    acceptStates.Add(renamer[state]);
            return acceptStates;
        }

        public Dfa ToDfa()
        {
            IDictionary<Set<int>, IDictionary<String, Set<int>>>
              cDfaTrans = CompositeDfaTrans(startState, trans);
            Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);
            ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;
            IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);
            IDictionary<int, IDictionary<String, int>> simpleDfaTrans =
              Rename(renamer, cDfaTrans);
            int simpleDfaStart = renamer[cDfaStart];
            Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);
            return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);
        }

        // Nested class for creating distinctly named States when constructing NFAs

        public class NameSource
        {
            private static int nextName = 0;

            public int next()
            {
                return nextName++;
            }
        }

        // Write an input file for the dot program.  You can find dot at
        // http://www.research.att.com/sw/tools/graphviz/

        public void WriteDot(String filename)
        {
            TextWriter wr =
              new StreamWriter(new FileStream(filename, FileMode.Create,
                                              FileAccess.Write));
            wr.WriteLine("// Format this file as a Postscript file with ");
            wr.WriteLine("//    dot " + filename + " -Tps -o out.ps\n");
            wr.WriteLine("digraph nfa {");
            wr.WriteLine("size=\"11,8.25\";");
            wr.WriteLine("rotate=90;");
            wr.WriteLine("rankdir=LR;");
            wr.WriteLine("start [style=invis];");    // Invisible start node
            wr.WriteLine("start -> d" + startState); // Edge into start state

            // The accept state has a double circle
            wr.WriteLine("d" + exitState + " [peripheries=2];");

            // The transitions 
            foreach (KeyValuePair<int, ArrayList<Transition>> entry in trans)
            {
                int s1 = entry.Key;
                foreach (Transition s1Trans in entry.Value)
                {
                    String lab = s1Trans.lab ?? "eps";
                    int s2 = s1Trans.target;
                    wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");
                }
            }
            wr.WriteLine("}");
            wr.Close();
        }
    }

    // Class Transition, a transition from one state to another ----------

    public class Transition
    {
        public readonly String lab;
        public readonly int target;

        public Transition(String lab, int target)
        {
            this.lab = lab; this.target = target;
        }

        public override String ToString()
        {
            return "-" + lab + "-> " + target;
        }
    }

}
